/**
 *  @file    DevideLink.c
 *  @brief   按位序奇偶性分解带头结点单链表
 *  @details 演示：
 *           1) 链表初始化、尾插法建表
 *           2) 单遍历同时拆分：奇数位→表 A，偶数位→表 B
 *           3) 顺序打印两条结果链
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025‑07‑14 18:30
 *  @version 1.1
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 节点结构定义 -------------------------

/**
 * @brief 单链表节点结构体
 */
typedef struct node {
    int           data;   ///< 数据域
    struct node  *next;   ///< 指针域
} node, *link;            ///< link 为 node* 类型别名，书写简洁

// ------------------------- 创建节点 -------------------------

/**
 * @brief 申请并初始化一个新节点
 * @param value  节点要保存的整数值
 * @return 成功返回新节点指针；失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;           // 内存不足
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// ------------------------- 初始化链表 -------------------------

/**
 * @brief 创建仅含头结点的空链表
 * @param head  指向链表头指针的指针
 * @note  头结点 data 字段可做计数或哑元，这里简单置 0
 */
void initNode(link *head) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return;
    newNode->data = 0;
    newNode->next = NULL;
    *head = newNode;
}

// ------------------------- 尾插法 -------------------------

/**
 * @brief 尾插法插入新节点
 * @param head   链表头结点指针
 * @param value  要插入的数据
 * @note  复杂度 O(n)，可通过维护尾指针优化
 */
void insertTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 顺序打印链表所有数据节点
 * @param head  链表头结点指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;                       // 跳过头结点
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 分解链表 -------------------------

/**
 * @brief 将原链表按位序奇偶拆分为 A、B 两表
 * @param head      原链表头结点指针（拆分后成为奇数位表 A）
 * @param evenHead  偶数位表 B 的头结点指针
 * @details
 *   单指针 cur 顺序扫描，oddTail / evenTail 分别拉住 A、B 的尾部：
 *   若当前结点序号为奇数，则接到 A；否则接到 B。保持相对次序不变。
 * @complexity 时间 O(n)；空间 O(1)
 */
void divideLink(link head, link evenHead) {
    if (head == NULL || head->next == NULL) return;

    link cur       = head->next;   // 当前扫描节点
    link oddTail   = head;         // A 表尾指针
    link evenTail  = evenHead;     // B 表尾指针
    int  index     = 1;            // 逻辑位序（从 1 开始）

    while (cur != NULL) {
        link next = cur->next;     // 预存下一节点，防断链

        if (index & 1) {           // 奇数位
            oddTail->next = cur;
            oddTail       = cur;
        } else {                   // 偶数位
            evenTail->next = cur;
            evenTail       = cur;
        }

        cur = next;
        ++index;
    }
    /* 尾端封口，防止环链或脏指针 */
    oddTail->next  = NULL;
    evenTail->next = NULL;
}

// ------------------------- 主函数 -------------------------

/**
 * @brief 测试链表奇偶拆分功能
 */
int main() {
    /* 构造原链表：1 → 2 → 3 */
    link head = NULL;
    initNode(&head);
    insertTail(head, 1);
    insertTail(head, 2);
    insertTail(head, 3);

    /* 创建偶数位链表头结点并执行拆分 */
    link evenHead = NULL;
    initNode(&evenHead);
    divideLink(head, evenHead);

    /* 预期输出：
     * A 表（奇数位）：1 3
     * B 表（偶数位）：2
     */
    puts("List A (odd indices):");
    printList(head);

    puts("List B (even indices):");
    printList(evenHead);

    return 0;
}
